#include <bits/stdc++.h>
using namespace std;

template<typename T>
void input(vector<T> & v, int n){
	v.assign(n + 1, {});
	for(int i=1;i<=n;++i) cin >> v[i];
	return;
}

template<typename T>
istream & operator >> (istream & is, vector<T> & v) {
	for(auto & i : v) is >> i;
	return is;
}

namespace IO{

char *__abc147, *__xyz258, __ma369[1000000];
#define __hv007() ((__abc147==__xyz258) && (__xyz258=(__abc147=__ma369)+fread(__ma369,1,100000,stdin),__abc147==__xyz258) ? EOF : *__abc147++)

int getInt(){
	int sgn = 1;
	char ch = __hv007();
	while( ch != '-' && ( ch < '0' || ch > '9' ) ) ch = __hv007();
	if ( '-' == ch ) {sgn = 0;ch=__hv007();}
 
	int ret = (int)(ch-'0');
	while( '0' <= (ch=__hv007()) && ch <= '9' ) ret = ret * 10 + (int)(ch-'0');
	return sgn ? ret : -ret;
}

using llt = long long;

llt getLL(){
	int sgn = 1;
	char ch = __hv007();
	while( ch != '-' && ( ch < '0' || ch > '9' ) ) ch = __hv007();
	if ( '-' == ch ) {sgn = 0;ch=__hv007();}
 
	llt ret = (int)(ch-'0');
	while( '0' <= (ch=__hv007()) && ch <= '9' ) ret = ret * 10LL + (llt)(ch-'0');
	return sgn ? ret : -ret;    
}

char getChar(function<bool(char)> ok){
    char ch = __hv007();
    while(!ok(ch)) ch = __hv007();
    return ch;
}

int getString(char s[], function<bool(char)> ok){
    char * p = s;
    *p++ = getChar(ok);
    for(char ch=__hv007();ok(ch);ch=__hv007()) *p++ = ch;
    return p - s;    
}


char __pq981[1000000];
char const * const __rs721 = __pq981 + 1000000;
char * __qw752 = __pq981;

#define __ge(c) (__qw752 == __rs721 ? fwrite(__pq981, 1, 1000000, stdout), __qw752 = __pq981 + 1, *__pq981 = (c) : *__qw752++ = (c))

void putChar(char c){__ge(c);}

void putULL(long long x){
    if(x == 0) return (void)(__ge('0'));

    char st[25];
	int top = 0;
	while(x){
		st[top++] = x % 10 + '0';
		x /= 10;
	} 
	while(top) __ge(st[--top]);
	return;
}

void finish(){
	fwrite(__pq981, 1, __qw752 - __pq981, stdout);
}

}

